%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%										
%% Sudoku solver							
%%				
%% Carl Regårdh, Oktober 2012		
%%
%% Input is given as nine lists (each with nine elements) 
%% where each list is treated as a row in the matrix.
%%
%% The example below should answer TRUE, since it represents a valid
%% sudoku solution:
%% sudoku([4,1,3,6,2,7,5,8,9], [7,8,5,9,4,1,3,2,6], [2,9,6,5,3,8,4,1,7], [5,7,2,8,9,6,1,4,3], [9,4,1,7,5,3,2,6,8], [6,3,8,4,1,2,7,9,5], [3,2,9,1,6,5,8,7,4], [8,5,4,2,7,9,6,3,1], [1,6,7,3,8,4,9,5,2]).
%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% Simple print helper predicate to give clean output to the user.
print([]).
print([H|T]) :- write(H), nl, print(T).

%% This predicate simply returns the length of a list.
%% X = the number at which we start counting (should always be zero).
%% Y = the length of the list.
len([], X, X).
len([H|T], X, Y) :- X1 is X + 1, len(T, X1, Y), !. %% Måste ha cut där för annars blir den aldrig klar, bara räknar upp hela tiden.

%% This predicate generates the numbers for the empty cells by checking if they are members of the list, 
%% if not they will be assigned.
done(L) :- member(1, L),
			member(2, L),
			member(3, L),
			member(4, L),
			member(5, L),
			member(6, L),
			member(7, L),
			member(8, L),
			member(9, L).

%% Returns true if the element X is not found in the list Y, uses
%% primitive predicate member to do so.
not_member(X,Y) :- member(X,Y), !, fail.
not_member(X,Y).

%% This predicate generates a row of numbers.
sudokuRow(L) :- len(L, 0, 9), done(L).

%% Checks if the list contains any element more then once, uses not_member to do so.
noDoubles([]).
noDoubles([H|T]) :- not_member(H, T), noDoubles(T).

%% Simply checks if any column has any duplicate integers, uses noDoubles to do so.
checkAllColumns([],[],[],[],[],[],[],[],[]).
checkAllColumns([H|S], [H2|S2], [H3|S3], [H4|S4], [H5|S5], [H6|S6], [H7|S7], [H8|S8], [H9|S9]) :- noDoubles([H, H2, H3, H4, H5, H6, H7, H8, H9]),
																										checkAllColumns(S, S2, S3, S4, S5, S6, S7, S8, S9).
			
%% Checks three sub-matrices for duplicates, uses noDoubles to do so.																						   
checkThreeBoxes([],[],[]).
checkThreeBoxes([A1, A2, A3|T1], [B1, B2, B3|T2], [C1, C2, C3|T3]) :- noDoubles([A1, A2, A3, B1, B2, B3, C1, C2, C3]),
																		  checkThreeBoxes(T1, T2, T3).
																		  
%% Checks all 9 sub-matrices for duplicates, this is only a wrapper predicate that uses checkThreeBoxes.
checkAllBoxes(A, B, C, D, E, F, G, H, I) :- checkThreeBoxes(A, B, C),
											  checkThreeBoxes(D, E, F),
											  checkThreeBoxes(G, H, I).

%% The main predicate, generates 9 rows, then checks the grid to see if any column or sub-matrix contains duplicates. 
%% Rows do not need to be checked for duplicates because of how they are generated in the first place.
%% Returns true when no column, row or sub-matrix contains duplicates.
sudoku(A, B, C, D, E, F, G, H, I) :- sudokuRow(A),
									  sudokuRow(B),
									  sudokuRow(C),
									  sudokuRow(D),
									  sudokuRow(E),
									  sudokuRow(F),
									  sudokuRow(G),
									  sudokuRow(H),
									  sudokuRow(I),
									  checkAllColumns(A, B, C, D, E, F, G, H, I),
									  checkAllBoxes(A, B, C, D, E, F, G, H, I),
									  print([A, B, C, D, E, F, G, H, I]).

%% And we are done! :)

